package com.bigshen.algorithm.eTwoPointer.solution02ThreeSum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
 *
 * Notice that the solution set must not contain duplicate triplets.
 *
 * Example 1:
 *
 * Input: nums = [-1,0,1,2,-1,-4]
 * Output: [[-1,-1,2],[-1,0,1]]
 * Example 2:
 *
 * Input: nums = []
 * Output: []
 * Example 3:
 *
 * Input: nums = [0]
 * Output: []
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    public static void main(String[] args) {


        int[] array = {-1,0,1,2,-1,-4};
        List<List<Integer>> result = new Solution().threeSum(array);

        for (List<Integer> list : result) {
            System.out.println();
            for (Integer element : list) {
                System.out.println(element);
            }
        }
    }

    // 两种解决方案
    // 1. 暴力解法
    //  三层for循环、时间复杂度 O(N^3)
    // 2. 1层for循环，内部双指针 O(n^2)，双指针前先排序，因为不是返回下标
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList();

        if (null == nums || nums.length < 3) {
            return result;
        }
        // 排序
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                // 本次需要三者之和为0，当最小值为0，后续无需遍历
                break;
            }
            if (i-1>=0 && nums[i] == nums[i-1]) {
                // 去重
                continue;
            }
            int start = i+1;
            int end = nums.length-1;
            while(start < end) {
                int sum = nums[i] + nums[start] + nums[end];
                if (sum > 0) {
                    // 结果过大，值变小
                    end --;
                } else if (sum < 0) {
                    // 结果过小，值变大
                    start ++;
                } else {
                    // 相等
                    List<Integer> list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[start]);
                    list.add(nums[end]);
                    result.add(list);
                    start++;
                    end--;
                    while (start < end && nums[start] == nums[start-1]) {
                        // 去重，start继续右移
                        start ++;
                    }
                    while (start < end && nums[end] == nums[end+1]) {
                        // 去重,end继续左移
                        end --;
                    }
                }
            }
        }

        return result;

    }
}
